Largest 1-bordered square

Time: O(N^3); Space: O(N^2); medium

DESCRIPTION IS HERE: https://leetcode.com/problems/largest-1-bordered-square

Example 1:

Input: grid =

Output:

Explanation:

Example 2:

Input: grid =

Output:

Explanation:

Notes:

Hints:

1. Dynamic programming [O(N^3), O(N^2)]

[1]:

class Solution1(object):
    """
    Time: O(N^3)
    Space: O(N^2)
    """
    def largest1BorderedSquare(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        top, left = [a[:] for a in grid], [a[:] for a in grid]

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if not grid[i][j]:
                    continue
                if i:
                    top[i][j] = top[i-1][j] + 1
                if j:
                    left[i][j] = left[i][j-1] + 1

        for l in reversed(range(1, min(len(grid), len(grid[0]))+1)):
            for i in range(len(grid)-l+1):
                for j in range(len(grid[0])-l+1):
                    if min(top[i+l-1][j],
                           top[i+l-1][j+l-1],
                           left[i][j+l-1],
                           left[i+l-1][j+l-1]) >= l:
                        return l*l

        return 0

[2]:

s = Solution1()

grid =
assert s.largest1BorderedSquare(grid) ==

grid =
assert s.largest1BorderedSquare(grid) ==